// https://www.lintcode.com/problem/combinations

public class Solution {
    /**
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    public List<List<Integer>> combine(int n, int k) {
        // write your code here
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
          nums[i] = i + 1;
        }
        return dfs(nums, 0, k);
    }

    protected List<List<Integer>> dfs(int[] nums, int idx, int k) {
        List<List<Integer>> ret = new ArrayList<>();
        int len = nums.length - idx;
        if ((len < k) || (k == 0)) {
        } else if (k == 1) {
          for (int i = idx; i < nums.length; ++i) {
            ret.add(new ArrayList<>());
            ret.get(ret.size() - 1).add(nums[i]);
          }
        } else {
          for (int i = idx; i < nums.length; ++i) {
            List<List<Integer>> combs = dfs(nums, i + 1, k - 1);
            for (List<Integer> comb : combs) {
              ret.add(new ArrayList<>());
              List<Integer> r = ret.get(ret.size() - 1);
              r.add(nums[i]);
              for (Integer v : comb) {
                r.add(v);
              }
            }
          }
        }
        return ret;
    }
}